//给你一个按升序排序的整数数组 num（可能包含重复数字），请你将它们分割成一个或多个长度至少为 3 的子序列，其中每个子序列都由连续整数组成。 
//
// 如果可以完成上述分割，则返回 true ；否则，返回 false 。 
//
// 
//
// 示例 1： 
//
// 
//输入: [1,2,3,3,4,5]
//输出: True
//解释:
//你可以分割出这样两个连续子序列 : 
//1, 2, 3
//3, 4, 5
// 
//
// 示例 2： 
//
// 
//输入: [1,2,3,3,4,4,5,5]
//输出: True
//解释:
//你可以分割出这样两个连续子序列 : 
//1, 2, 3, 4, 5
//3, 4, 5
// 
//
// 示例 3： 
//
// 
//输入: [1,2,3,4,4,5]
//输出: False
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 10000 
// 
// Related Topics贪心 | 数组 | 哈希表 | 堆（优先队列） 
//
// 👍 388, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

class SplitArrayIntoConsecutiveSubsequences {
    public static void main(String[] args) {
        Solution solution = new SplitArrayIntoConsecutiveSubsequences().new Solution();
        solution.isPossible(new int[]{1, 2, 3, 4, 4, 5});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // https://labuladong.gitee.io/algo/4/33/125/
        public boolean isPossible(int[] nums) {
            Map<Integer, Integer> freq = new HashMap<>();   // 记录出现的次数
            Map<Integer, Integer> need = new HashMap<>();   // 记录下一个需要什么数字

            // 统计频率
            for (int num : nums) freq.put(num, freq.getOrDefault(num, 0) + 1);

            for (int i = 0; i < nums.length; i++) {
                // 此时已经被别人选走
                int num = nums[i];
                if (freq.get(num) == 0) {
                    continue;
                }

                // 有序列需要，可以合并在后边
                if (need.containsKey(num) && need.get(num) > 0) {
                    freq.put(num, freq.getOrDefault(num, 0) - 1);
                    need.put(num, need.getOrDefault(num, 0) - 1);
                    // 更新下一个需要的数字
                    need.put(num + 1, need.getOrDefault(num + 1, 0) + 1);
                }

                // 如果不能合并在某个序列后边，判断是否可以单独成一个最少3位数的序列
                else if (freq.containsKey(num) && freq.containsKey(num + 1) && freq.containsKey(num + 2) && freq.get(num + 1) > 0 && freq.get(num + 2) > 0) {
                    freq.put(num, freq.getOrDefault(num, 0) - 1);
                    freq.put(num + 1, freq.getOrDefault(num + 1, 0) - 1);
                    freq.put(num + 2, freq.getOrDefault(num + 2, 0) - 1);
                    need.put(num + 3, need.getOrDefault(num + 3, 0) + 1);
                } else return false;
            }

            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
